#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/3/19
# @USER    : Shengji He
# @File    : LongestNiceSubarray.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List

"""
- Array
- Bit Manipulation
- Sliding Window
"""


class Solution:
    """
    You are given an array nums consisting of positive integers.

    We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.

    Return the length of the longest nice subarray.

    A subarray is a contiguous part of an array.

    Note that subarrays of length 1 are always considered nice.

    Example 1:
        Input: nums = [1,3,8,48,10]
        Output: 3
        Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:
        - 3 AND 8 = 0.
        - 3 AND 48 = 0.
        - 8 AND 48 = 0.
        It can be proven that no longer nice subarray can be obtained, so we return 3.

    Example 2:
        Input: nums = [3,1,5,11,13]
        Output: 1
        Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.

    Constraints:
        - 1 <= nums.length <= 105
        - 1 <= nums[i] <= 109
    """

    def longestNiceSubarray(self, nums: List[int]) -> int:
        last_pos = [-1] * 30  # 记录每个二进制位最后出现的位置
        max_len = 1
        left = 0  # 滑动窗口的左边界
        for right in range(len(nums)):
            num = nums[right]
            current_max_pos = left - 1  # 初始化为左边界前一个位置

            # 找出当前数字的所有置1的位
            bits = []
            for i in range(30):
                if (num >> i) & 1:
                    bits.append(i)

            # 遍历这些位，找到最大的last_pos（需大于等于当前左边界）
            for b in bits:
                if last_pos[b] >= left and last_pos[b] > current_max_pos:
                    current_max_pos = last_pos[b]

            # 更新左边界
            left = current_max_pos + 1

            # 更新这些位的最后出现位置为当前右指针
            for b in bits:
                last_pos[b] = right
            current_length = right - left + 1

            # 计算当前窗口长度
            if current_length > max_len:
                max_len = current_length
        return max_len

    def longestNiceSubarray_v2(self, nums: List[int]) -> int:
        temp = 0  # 用于记录当前窗口内所有元素的按位或结果
        left = 0  # 滑动窗口的左指针
        result = 0  # 记录最长子数组的长度
        for right, num in enumerate(nums):
            # 当新元素与当前窗口的位存在冲突时，右移左指针
            while num & temp:
                temp ^= nums[left]  # 异或操作移除左指针处的元素
                left += 1
            # 更新最长子数组长度
            result = max(result, right - left + 1)
            temp |= num  # 将当前元素加入窗口的位记录
        return result


if __name__ == '__main__':
    nums = [1, 3, 8, 48, 10]

    S = Solution()
    print(S.longestNiceSubarray(nums))
    print(S.longestNiceSubarray_v2(nums))
    print('done')
